package com.bichengcao.googlecodejam.gcj2008beta;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashMap;

public class RandomRoute {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/gcj2008beta/C-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/gcj2008beta/RandomRoute.out", outputs);
	}

	static class Input {

		int numRoads;
		String startingCity;
		Road[] roads;
	}

	static class Road {

		int id;
		String startCity;
		String endCity;
		int time;
	}
	
	static class City {
		
		String name;
		int distance = Integer.MAX_VALUE;
		int routes;
		ArrayList<Road> outRoads = new ArrayList<Road>();
		ArrayList<Road> inRoads = new ArrayList<Road>();
		
		City(String name) {
			this.name = name;
		}
	}

	static class Output {

		double[] probabilities;
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.numRoads = Integer.parseInt(splits[0]);
			input.startingCity = splits[1];
			input.roads = new Road[input.numRoads];
			for (int j = 0; j < input.numRoads; j++) {
				line = in.readLine();
				splits = line.split(" ");
				input.roads[j] = new Road();
				input.roads[j].id = j;
				input.roads[j].startCity = splits[0];
				input.roads[j].endCity = splits[1];
				input.roads[j].time = Integer.parseInt(splits[2]);
			}
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static HashMap<String, City> cities;
	
	private static Output process(Input input) {
		Output output = new Output();

		// Construct the graph
		cities = new HashMap<String, City>();
		for (Road road : input.roads) {
			City city = cities.get(road.startCity);
			if (city == null) {
				city = new City(road.startCity);
				cities.put(road.startCity, city);
			}
			city.outRoads.add(road);
			
			city = cities.get(road.endCity);
			if (city == null) {
				city = new City(road.endCity);
				cities.put(road.endCity, city);
			}
			city.inRoads.add(road);
		}
		
		// Dijkstra's algorithm
		cities.get(input.startingCity).distance = 0;
		cities.get(input.startingCity).routes = 1;
		ArrayList<City> targetCities = new ArrayList<City>();
		ArrayList<City> Q = new ArrayList<City>(cities.values());
		while (Q.size() > 0) {
			int minDistance = Q.get(0).distance;
			int u = 0;
			for (int i = 1; i < Q.size(); i++) {
				if (Q.get(i).distance < minDistance) {
					minDistance = Q.get(i).distance;
					u = i;
				}
			}
			if (Q.get(u).distance == Integer.MAX_VALUE) {
				break;
			}
			City city = Q.get(u);
			targetCities.add(Q.get(u));
			Q.remove(u);
			for (Road road : city.outRoads) {
				City targetCity = cities.get(road.endCity);
				targetCity.distance = Math.min(targetCity.distance, city.distance + road.time);
			}
		}
		
		// Calculate probabilities
		targetCities.remove(cities.get(input.startingCity));
		output.probabilities = new double[input.numRoads];
		
		for (City city : targetCities) {
			countRoutes(city);
		}
		
		for (City city : targetCities) {
			calculateProbability(city, 1.0 / targetCities.size(), output.probabilities);
		}

		return output;
	}

	private static int countRoutes(City city) {
		if (city.routes != 0) {
			return city.routes;
		}
		int result = 0;
		for (Road road : city.inRoads) {
			if (cities.get(road.startCity).distance + road.time == city.distance) {
				result += countRoutes(cities.get(road.startCity));
			}
		}
		return city.routes = result;
	}

	private static void calculateProbability(City city, double probability, double[] result) {
		if (city.distance == 0) return;
		for (Road road : city.inRoads) {
			if (cities.get(road.startCity).distance + road.time == city.distance) {
				result[road.id] += probability / city.routes * cities.get(road.startCity).routes;
				calculateProbability(cities.get(road.startCity),
						probability / city.routes * cities.get(road.startCity).routes, result);
			}
		}
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		DecimalFormat df = new DecimalFormat("0.0000000");
		for (int i = 0; i < N; i++) {
			out.print("Case #" + (i + 1) + ":");
			for (int j = 0; j < outputs[i].probabilities.length; j++) {
				out.print(" " + df.format(outputs[i].probabilities[j]));
			}
			out.println();
		}
		out.close();
	}

}
